#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    deque<int> q;
    void max_pop(int num)
    {
        if (!q.empty() && num == q.front())
            q.pop_front();
    }
    void max_push(int num)
    {
        while (!q.empty() && q.back() < num)
            q.pop_back();
        q.push_back(num);
    }
    int get_max_num()
    {
        return q.front();
    }
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ret;
        for (int i = 0; i < k; i++)
            max_push(nums[i]);
        ret.push_back(get_max_num());
        int tmp = k;
        while (tmp < nums.size())
        {
            max_pop(nums[tmp - k]);
            max_push(nums[tmp++]);
            ret.push_back(get_max_num());
        }
        return ret;
    }
};

class Solution {
public:
    class topless
    {
    public:
        bool operator()(const pair<int, int>& x, const pair<int, int>& y)
        {
            return x.second < y.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> ret;
        unordered_map<int, int> um;
        for (auto e : nums)
            um[e]++;
        priority_queue<pair<int, int>, vector<pair<int, int>>, topless> pq;
        for (auto e : um)
        {
            pq.push(make_pair(e.first, e.second));
        }
        for (int i = 0; i < k; i++)
        {
            ret.push_back(pq.top().first);
            pq.pop();
        }
        return ret;
    }
};